package com.Questions.DP;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Random;

import java.util.Collections;

/**
 *  最长回文子串
 */
public class leetcode5 {
    // 根据回文串的特点 得出 当一个字符串是回文串的时候
    // 那么 去掉最前面的和最后面的字符串的时候 结果仍然是字符串
    // 所以可以写出动态规划的状态转移方程
    // P(i,j)=P(i+1,j-1)^(Si==Sj)
    //也就是说，只有 s[i+1:j−1] 是回文串
    // 并且 s 的第 i 和 j个字母相同时
    // s[i:j] 才会是回文串
    // 边界条件
    // P(i,i)=true
    // P(i,i+1)=(Si==Sj)

    public String longestPalindrome(String s) {
        int len=s.length();
        if(len<2){
            return s;
        }
        // 回文字符串的最大长度
        int maxLen=1;
        int begin=0;
        boolean[][] dp=new boolean[len][len];
        for(int i=0;i<len;++i){
            // 初始化 所有长度为1 的子串都是回文串
            dp[i][i]=true;
        }
        char[] charArray = s.toCharArray();
        // 枚举字符串的长度
        // 从字符串的长度枚举 逻辑就是 字符串较长的时候能通过动态规划状态转移方程
        // 利用字符串较短时得到的结果
        for(int L=2;L <= len;L++){
            for(int i = 0;i < len ;++i){
                int j=L+i-1;
                if(j>=len){
                    break;
                }
                if(charArray[i]!=charArray[j]){
                    dp[i][j]=false;

                }else{
                    if(j-i<3){
                        dp[i][j]=true;
                    }else{
                        dp[i][j]=dp[i+1][j-1];
                    }
                }
                if(dp[i][j]&&j-i+1>maxLen){
                    maxLen=j-i+1;
                    begin=i;
                }
            }
        }
        return s.substring(begin,begin+maxLen);
    }

}
